package leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

public class _394_DecodeString {
    public static void main(String[] args) {
        Solution solution = new _394_DecodeString().new Solution();
        String s = "3[a2[c]]";
        String s1 = solution.decodeString(s);
        System.out.println(s1);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 存字符串的栈
        Deque<String> stack1 = new LinkedList<>();
        // 存数字的栈
        Deque<Integer> stack2 = new LinkedList<>();
        int idx = 0;

        /**
         * 获得数字
         *
         * @param s 字符串
         * @return 数字
         */
        public Integer getNum(String s) {
            StringBuilder sb = new StringBuilder();
            while (Character.isDigit(s.charAt(idx))) {
                sb.append(s.charAt(idx));
                idx++;
            }
            return Integer.parseInt(sb.toString());
        }

        /**
         * @return 当前 stack1 中的 StringBuider
         */
        public StringBuilder getStringBuider() {
            StringBuilder tmp1 = new StringBuilder();
            while (!stack1.isEmpty() && !stack1.peek().equals("[")) {
                tmp1.append(stack1.peek());
                stack1.pop();
            }
            return tmp1;
        }

        public String decodeString(String s) {
            while (idx < s.length()) {
                char c = s.charAt(idx);
                if (Character.isDigit(c)) {
                    Integer num = getNum(s);
                    stack2.push(num);
                } else if (Character.isLetter(c) || c == '[') {
                    stack1.push(String.valueOf(c));
                    idx++;
                } else if (c == ']') {
                    StringBuilder tmp1 = getStringBuider();
                    // "[" 出栈
                    stack1.pop();

                    int num = stack2.peek();
                    // 数字出栈
                    stack2.pop();
                    StringBuilder tmp2 = new StringBuilder();
                    for (int i = 0; i < num; i++) {
                        tmp2.append(tmp1);
                    }
                    stack1.push(tmp2.toString());
                    idx++;
                }
            }
            StringBuilder res = getStringBuider();
            res.reverse();
            return res.toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}